Error-Correcting Codes
A fundamental problem in the field of data storage and communication is constructing efficient error-correcting codes. Unless specified otherwise, any reference to a “code” in the following description should be understood to refer to an error-correcting code.
One very important error-correcting code is a linear block error-correcting code.
This code encodes a block of k information symbols using a block of N symbols, where N>k. The additional N−k symbols are used to correct corrupted signals when they are received over a noisy communication channel or retrieved from faulty storage media. The parameter k is called the “dimension” of the code.
A block of N symbols that satisfies all the constraints of the code is called a “code-word,” and the corresponding block of k information symbols is called an “information block.”
A linear code can be represented by a parity check matrix. The parity check matrix representing a binary [N, k] code is a matrix of zeros and ones, with M rows and N columns. The N columns of the parity check matrix correspond to the N symbols of the code. The number of linearly independent rows in the matrix is N−k.
LDPC Codes
There has recently been a great deal of interest in codes that can be decoded using iterative methods. One particularly important iteratively-decodable code is a low-density parity-check (LDPC) code, first described in 1963 by Gallager, see T. Richardson and R. Urbanke, “The Renaissance of Gallager's Low-Density Parity-Check Codes,” IEEE Communications Magazine, vol. 41, pp. 126-131, August 2003, and U.S. Pat. No. 6,633,856 to Richardson et al. on Oct. 14, 2003, “Methods and apparatus for decoding LDPC codes.”
Many LDPC codes use random constructions. For example, Gallager's original binary LDPC code is defined in terms of a parity check matrix, which consists only of 0's and 1's, where a small number of 1's are placed randomly within the matrix according to a pre-defined probability distribution. In general, iterative decoders work well for codes with a parity check matrix that has a relatively small number of non-zero entries, whether that parity check matrix has a random or regular construction.
LDPC codes are often represented using “Tanner graphs,” which are equivalent to parity check matrices. In a Tanner graph, columns of the parity check matrix are represented as “bit nodes” while rows of the parity check matrix are represented as “check nodes.” The Tanner graph is a bi-partite graph that contains a connection between a bit node and a check node if there is a 1 in the parity check matrix at the corresponding row and column position.
QC-LDPC Codes
LDPC codes based on random constructions have the disadvantage that the wiring complexity involved in fabricating a hardware decoder is prohibitive. For this reason, the more regular “quasi-cyclic” LDPC (QC-LDPC) codes have been developed. An example of a QC-LDPC code is described by R. M. Tanner, D. Sridhara, and T. Fuja, “A Class of Group-Structured LDPC Codes,” Proc. International Symposium on Communication Theory and Applications, Ambleside, U.K., July 2001, US Patent Publications 20060109821, “Apparatus and method capable of a unified quasi-cyclic low-density parity-check structure for variable code rates and sizes,” and US Patent Publication 20050149845 “Method of constructing QC-LDPC codes using qth-order power residue.”
The regular structure of QC-LDPC codes enables efficient and high-speed very large scale integration (VLSI) implementations. For this reason, a number of wireless communications standards use QC-LDPC codes, e.g., the IEEE 802.16e, 802.11n standards and DVB-S2 standards.
In general, QC-LDPC codes are in the form of a parity-check matrix H that has a special structure, which makes the codes very convenient for hardware implementation. The parity check matrix is constructed out of square p×p sub-matrices. These sub-matrices either consist of all zeroes, or they are circulant permutation matrices.
Circulant permutation matrices are matrices with a single 1 in each row, where the column in which the 1 is located is shifted by one from row to row. The following matrix is an example of a circulant permutation matrix with p=6:
                              I          ⁡                      (            2            )                          =                              (                                                            0                                                  0                                                  1                                                  0                                                  0                                                  0                                                                              0                                                  0                                                  0                                                  1                                                  0                                                  0                                                                              0                                                  0                                                  0                                                  0                                                  1                                                  0                                                                              0                                                  0                                                  0                                                  0                                                  0                                                  1                                                                              1                                                  0                                                  0                                                  0                                                  0                                                  0                                                                              0                                                  1                                                  0                                                  0                                                  0                                                  0                                                      )                    .                                    (        1        )            
This matrix is called “I(2)” because when the rows and columns are counted starting at position 0, the 1 in the 0th row is in column 2. The permutation matrix I(0) is the identity matrix. If the value of the index t in I(t) is greater than or equal to p, then the matrix wraps around, so that for p=6, we have I(2)=I(8)=I(14) etc. One special notation that is generally used in describing QC-LDPC codes, and which is used herein, is that the p×p all-zeroes matrix is denoted I(−1).
A (J, L) QC-LDPC code with sub-matrices of size p×p is defined by its parity check matrix
                              H          =                      [                                                                                I                    ⁡                                          (                                              p                                                  0                          ,                          0                                                                    )                                                                                                            I                    ⁡                                          (                                              p                                                  0                          ,                          1                                                                    )                                                                                        …                                                                      I                    ⁡                                          (                                              p                                                  0                          ,                                                      L                            -                            1                                                                                              )                                                                                                                                        I                    ⁡                                          (                                              p                                                  1                          ,                          0                                                                    )                                                                                                            I                    ⁡                                          (                                              p                                                  1                          ,                          1                                                                    )                                                                                        …                                                                      I                    ⁡                                          (                                              p                                                  1                          ,                                                      L                            -                            1                                                                                              )                                                                                                                    ⋮                                                  ⋮                                                  ⋱                                                  ⋮                                                                                                  I                    ⁡                                          (                                              p                                                                              J                            -                            1                                                    ,                          0                                                                    )                                                                                                            I                    ⁡                                          (                                              p                                                                              J                            -                            1                                                    ,                          1                                                                    )                                                                                        …                                                                      I                    ⁡                                          (                                              p                                                                              J                            -                            1                                                    ,                                                      L                            -                            1                                                                                              )                                                                                            ]                          ,                            (        2        )            where 0≦j≦J−1, 0≦l≦L−1, and pj,l is an integer in the range −1≦pj,l≦p−1. For a parity check matrix of size M by N, N=pL and m=pJ.
A specific QC-LDPC parity check matrix can be constructed form a corresponding J×L dimensional base matrix B. The entries in the base matrix are the values pj,l for the corresponding entry of the parity check matrix:
                    B        =                              [                                                                                p                                          0                      ,                      0                                                                                                            p                                          0                      ,                      1                                                                                        …                                                                      p                                          0                      ,                                              L                        -                        1                                                                                                                                                              p                                          1                      ,                      0                                                                                                            p                                          1                      ,                      1                                                                                        …                                                                      p                                          1                      ,                                              L                        -                        1                                                                                                                                          ⋮                                                  ⋮                                                  ⋱                                                  ⋮                                                                                                  p                                                                  J                        -                        1                                            ,                      0                                                                                                            p                                                                  J                        -                        1                                            ,                      1                                                                                        …                                                                      p                                                                  J                        -                        1                                            ,                                              L                        -                        1                                                                                                                  ]                    .                                    (        3        )            
When all-zeroes sub-matrices are used, the resulting LDPC code can be an “irregular” LDPC code. An irregular LDPC code is one for which different columns or rows in the parity check matrix can contain different numbers of ones.
Girth of LDPC Codes
Depending on the application, LDPC codes are designed to optimize performance in either the “water-fall” (SNR near the code threshold) or “error-floor” (higher SNR) regime, or both. Low error floors are particularly important for applications that have extreme reliability demands, such as data storage devices and communication systems.
Some theoretical analyses of error floor problems for LDPC codes argue that error events are caused by “trapping sets,” see for example, T. J. Richardson, “Error Floors of LDPC Codes,” Proc. 41st Annual Allerton Conference on Communications, Control, and Computing 2003. Trapping sets result from clusters of short cycles in the Tanner graph of the code. One way to remove trapping sets that involve short cycles is to carefully design the clustering of short cycles in the Tanner graph.
A simpler approach uses codes with larger girths. The “girth” of a code is the length of a shortest cycle in the code graph. By removing short cycles, a large number of cycles are removed, which has the effect of lowering (improving) the error floor.
There is considerable prior art on optimizing girth in LDPC codes. One code uses a progressive-edge growth (PEG) method, see X. Y. Hu, E. Eleftheriou, and D. M. Arnold, “Regular and Irregular Progressive Edge-Growth Tanner Graphs,” IEEE Trans. Info. Theory, vol. 51, pp. 386-398, 2005.
There has also been work on applying the PEG method to QC-LDPC codes, see Z. Li, B. V. K. V. Kumar, “A Class of Good Quasi-cyclic low-density parity-check Codes Based on Progressive Edge Growth Graph,” Signals, Systems, and Computers, Conference Record of the 38th Asilomar Conference, vol. 2, pp. 1990-1994, 2004.
High-girth QC-LDPC codes can also be constructed using a random “guess-and-test” method, see M. P. C. Fossorier, “Quasi-cyclic low-density parity-check codes from circulant permutation matrices,” IEEE Trans. Inform. Theory, vol. 50, no. 8, pp. 1788-1793, August 2004.
However, there is room for improvement in those methods, in terms of the girth that can be achieved for a code of particular block-length and dimension. Therefore, an improved method for constructing high-girth QC-LDPC codes is desired.